Na celou zkoušku jsou 2 hodiny + 10 minut na odevzdání v Moodle. Před začátkem testu se rozebírá zadání každé úlohy a upřesnění podmínek, tento čas se do vyřešení nezapočítává. Důkazy a zdůvodnění nemusí být ryze matematické a formální s ohledem na to, že jde o první ročník studia, ale doporučuje se co největší přesnost a jednoznačnost v popisu řešení. Lze používat materiály z kurzu Moodle, tj. prezentace, kód a nahrávky přednášek.
Úloha 1.
1. (10 bodů) Na vstupu je zadána posloupnost **kladných celých čísel **délky n. Navrhněte efektivní algoritmus, který určí, zdali v posloupnosti existuje **souvislý úsek **takový, že součet čísel v tomto úseku je stejný, jako součet čísel, které v něm neleží. Výstupem jsou
index prvního a index posledního prvku v úseku (pozice čísel ve vstupní posloupnosti číslujeme od 0) a součet jeho prvků či hodnota None, pokud takový neexistuje.
Má-li úloha více řešení, stačí nalézt jedno libovolné z nich. Navrhněte postup, jak správně vyřešit úlohu **s co nejlepší časovou a prostorovou složitostí **vzhledem k délce vstupní posloupnosti.
(a) Popište algoritmus (včetně datových struktur, které případně budete používat). Programový kód není povinný, slovní vysvětlení zvoleného postupu řešení naopak povinné je. Nepoužívejte prosím žádné netriviální datové struktury (jako jsou např. datové typy dictionary či set v jazyce Python), jejichž algoritmus sami nepopíšete a neodvodíte jeho časovou složitost.
(b) **Zdůvodněte správnost **algoritmu.
(c) Odvoďte **časovou a prostorovou složitost **(v **nejhorším **případě).
Příklad:
vstup: 5 2 2 6 12 11 7 10 2 5 2 8
výstup: 3 6 36
Úloha 2.
2. (10 bodů) Je zadán **binární strom **o n vrcholech, v nichž jsou uložena navzájem různá celá čísla, a dále celé číslo x. Navrhněte efektivní algoritmus, který vrátí seznam čísel uložených ve všech vrcholech, které leží v podstromu s kořenem obsahujícím číslo x.
(a) Svoje řešení zapište jako funkci v Pythonu, využijte **definici třídy **pro vrchol binárního stromu i **hlavičku funkce **uvedené níže a váš kód prosím opatřete komentáři,
(b) zdůvodněte správnost,
(c) odvoďte **časovou složitost **(v nejhorším případě).
class VrcholBinStromu:
"""třída pro reprezentaci vrcholu binárního stromu"""
def __init__(self, info = None, levy = None, pravy = None):
self.info = info # číslo vrcholu
self.levy = levy # levé dítě
self.pravy = pravy # pravé dítě
def podstrom(koren : VrcholBinStromu, x : int):
"""
koren : kořen zadaného binárního stromu
x : celé čislo
vrátí : seznam čísel uložených ve všech vrcholech, které leží v podstromu s kořenem obsahujícím číslo x
"""
Úloha 3.
Rozhodněte zda platí, své odpovědi vždy zdůvodněte.
(a) (5 bodů) Rozhodněte, zda platí: Pro libovolné dvě funkce f, g: N → R+ platí
f = O(g) **právě tehdy, když *log2 f = O( log2 g ).
Svoji odpověď zdůvodněte, tj. tvrzení dokažte (pokud platí) či sestrojte protipříklad (pokud neplatí). Nestačí jen napsat, že je to triviální či že to bylo na přednášce / cvičeních apod.
(b) (5 bodů) V binárním vyhledávacím stromu chceme implementovat operaci odebrání prvku s danou hodnotou klíče x následovně:
Vyhledáme ve stromu vrchol v s hodnotou *x *(předpokládejme, že to umíme a že se x skutečně ve stromu nachází) a pak opakovaně provádíme následující kroky výpočtu:
je-li vrchol v listem, odebereme ho ze stromu a tím celá operace končí
není-li vrchol v listem, označíme symbolem *s *jeho jedno dítě (levé, má-li obě)
hodnotu z vrcholu s zkopírujeme do vrcholu v
symbolem v nyní označíme vrchol s . **
Rozhodněte, zda výše popsaný postup korektně implementuje požadovanou operaci. Svoji odpověď zdůvodněte.**